home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Info 1994 March
/
Internet Info CD-ROM (Walnut Creek) (March 1994).iso
/
inet
/
internet-drafts
/
draft-ietf-isis-multilevel-routing-00.txt
< prev
next >
Wrap
Text File
|
1993-08-09
|
25KB
|
628 lines
ISIS Working Group Radia Perlman
Internet-draft Chris Gunner
Digital Equipment Corp.
June 1993
Multiple Levels of Hierarchy with IS-IS
Table of Contents
1. Status of this Memo 2
2. Abstract 2
3. Introduction 2
4. Topologies 3
5. Management 4
5.1. Port/Region Mapping 5
5.2. Address Summaries for Import Into Region 5
6. Extra Information in Control Packets 6
6.1. Hello, CSNP, PSNP 6
6.2. LSP 7
7. Using Address Summaries 7
8. Picking a Path 8
9. Working Group Information 9
10. Authors' Addresses 10
Perlman (Internet-Draft expires end December 1993) [Page 1]
Internet-Draft Multilevel IS-IS June 1993
1. Status of this Memo
This document is an Internet Draft describing changes to IS-IS
to enable it to support many levels of hierarchy. This should
apply to any network layer protocol routed by IS-IS. It is not a
finished specification. Instead it is a conceptual document,
intended to start discussion. If the basic premise is judged
sound, it should not be difficult to produce a specification.
Internet Drafts are working documents of the Internet
Engineering Task Force (IETF), its Areas, and its Working
Groups. Note that other groups may also distribute working
documents as Internet Drafts.
Internet Drafts are draft documents valid for a maximum of six
months. This Internet draft expires at the end of December 1993.
Internet drafts may be updated, replaced, or obsoleted by other
documents at any time. It is not appropriate to use Internet
Drafts as reference material or to cite them other than as a
"working draft" or "work in progress".
Please check the I-D abstract listing contained in each Internet
Draft directory to learn the current status of this or any other
Internet Draft.
This is a draft document of the ISIS working group.
Distribution of this memo is unlimited. Please send comments to
the ISIS working group:
isis@merit.edu
2. Abstract
This paper describes the management, algorithms, and control
packet structures necessary to support arbitrary levels of
routing hierarchy in IS-IS.
3. Introduction
IS-IS is written as though there were two levels of routing
hierarchy: level 1, which routes on ID, and level 2, which
routes on address prefix. IP and CLNP addressing both have the
ability to have multiple levels of hierarchy for "level 2"
routing. In IP this is done by summarizing addresses with a
shorter mask. In CLNP this is done by summarizing addresses with
a shorter address prefix. This document explains what is needed
in IS-IS to truly support as many levels of hierarchy as is
Perlman (Internet-Draft expires end December 1993) [Page 2]
Internet-Draft Multilevel IS-IS June 1993
possible in the address structure.
The main reason to provide multiple levels of hierarchy is for
scaling. However, the design in this paper also provides a lot
of the functionality that people expect from an inter-domain
routing protocol. It allows setting up policies for which
destinations are reachable from which portions of the network.
In cases where the topology and IS-IS can accommodate all the
necessary policies, it is desirable to run only a single routing
protocol, rather than needing both an intradomain and an
interdomain routing protocol.
The basic idea is that a network administrator can draw a
logical circle around any portion of the network. We'll call the
portion of the network inside the circle a "region". (I
apologize for making up a new term, but I want to prevent
confusion with existing terms, such as "area", or "subnetwork").
LSPs inside a region will not "leak out". LSPs from outside the
region will not "leak in". Information about addresses inside
the region will be explicitly advertised through configured
address summaries. Similarly, information about addresses
outside the region will be explicitly advertised through
configured address summaries.
For safety, ease of network troubleshooting, and flexibility in
such cases as links that should be included in multiple regions,
it is convenient to assign a name to a region. An option will be
added to IS-IS messages to include the region name. The goal is
that regions be as autoconfiguring as possible. Ideally, only
the routers on the boundary of a region will need to know
anything about the region. And in a network that is small enough
for a non-hierarchical level 2 network to keep track of
everything, there is no necessity to configure any region
information.
This design should be compatible with current implementations.
Although a router that has not implemented the design in this
document cannot be on the boundary of a region, it should
interoperate in a multi-level IS-IS net.
4. Topologies
This proposal really only concerns how to make level 2 routing
multi-level. It pertains to both IP and CLNP. Only CLNP has
true level 1 routing, (by the definition that a node has an ID
within a level 1 subnetwork and can have multiple links within
that level 1 subnetwork, or move within that level 1 subnetwork,
and always have just one network layer address). At any rate,
this proposal does not change level 1 routing -- it only changes
Perlman (Internet-Draft expires end December 1993) [Page 3]
Internet-Draft Multilevel IS-IS June 1993
the nature of level 2 routing. OSPF and IS-IS refer to "areas"
in the context of IP routing. This proposal makes IP areas
simply a special case of regions.
The basic idea is that the network will be partitioned by
network management into "regions". Each region will be assigned
a name, which will be a text string. LSPs do not leak between
areas, however, information about the destinations within a
region do get summarized and announced to other regions. The
summary addresses must be configured in order to get any
aggregation of addresses. Otherwise, all destinations would be
reported. For example, assume there is a region A and the
destinations in the region are 5.12.*, 5.17.*, and 5.22.15.*.
If R has a link in region A and a link in region B, R will
include information about the destinations in A in R's LSP in
region B. R might have been configured with the summary address
5.* for import into B, in which case it will include 5.* in its
LSP in B. If R has not been configured with a summary address,
it will report the destinations 5.12.*, 5.17.*, and 5.22.15.*.
For additional flexibility, a router can be configured to import
only the configured address summaries into one of its regions,
or be configured with summaries that it should not import into
that region.
A router can be in multiple regions, and a link can be in
multiple regions. The scheme is flexible so that region
boundaries can be done whichever way is most convenient. The way
region boundaries are marked is by configuring a router as to
which links are in which regions.
There is an unfortunate aspect of importing information between
regions, in that the counting-to-infinity behavior of distance
vector protocols manifests itself, and in a particularly ugly
way since each step of the counting-to-infinity behavior is done
by flooding of an LSP in a region. We could eliminate the
counting-to-infinity problem by constraining the topology in
various ways, or by making the protocol expensive and complex by
doing something like listing the entire path of regions from
which information originated. However, we are advocating merely
adding to the LSP information a count of the number of regions
through which the information was imported. This will alleviate
but not solve the counting-to-infinity problem. Further tuning
can be done by configuration of import/export rules.
5. Management
The design of the management for multilevel IS-IS has the
following goals:
Perlman (Internet-Draft expires end December 1993) [Page 4]
Internet-Draft Multilevel IS-IS June 1993
- Allow networks with simple topologies to autoconfigure as
much as possible.
- Allow sophisticated network managers in complex topologies
as much flexibility as possible.
- Allow nodes to be managed one at a time. The network should
do something sensible in all the intermediate states.
- Allow formation of a region by configuration of only the
routers in the boundary of the region.
5.1. Port/Region Mapping
We will define a "region" as a portion of the network that is
intended to be physically intact (we may or may not design
automatic region partition repair). It has a name, which is a
text string which can be optionally configured into routers that
are completely inside the region, but must be configured into
routers that have links to other regions. A router that has
links to other regions must be configured with names for each of
the regions to which it attaches, as well as a mapping between
links and regions. Something like the following:
region Alice: ports 1, 2, 7
region Bob: ports 3, 4
region Fred: port 5
region George: ports 6,7
Note that port 7 is in both regions George and Alice. It is
legal for a link to be in multiple regions. However, once a link
is in multiple regions, IS-IS packets transmitted over the link
must have the region name option included.
It is also legal to not configure a region name for some ports,
in which case all unconfigured ports are considered to be in the
same region, which is the unnamed region.
5.2. Address Summaries for Import Into Region
import summaries into Alice
(IP address, mask), cost
(IP address, mask), cost
...
Perlman (Internet-Draft expires end December 1993) [Page 5]
Internet-Draft Multilevel IS-IS June 1993
(IP address, mask), cost
(CLNP address prefix), cost
(CLNP address prefix), cost
...
(CLNP address prefix), cost
exception flag
(IP address, mask) is an IP address summary. (CLNP address
prefix) is a CLNP address prefix. Cost does not have to be
configured. If it is, then it is the cost advertised when that
summary is advertised. If cost is not configured, then the cost
of the nearest matching address is used as the cost to report to
that address summary. The "exception flag" states what should be
done about destinations that are reachable but are not included
in any of the configured address prefixes. If the flag is true,
then all remaining reachable destinations will be imported. If
the flag is false, then nothing other than configured address
prefixes will be imported.
It might be convenient to allow configuration of address
prefixes that are specifically disallowed, so for instance a
region might allow all addresses to be imported except for a
few.
Another item that might be desirable is to configure a region
count per address summary, to make the counting-to-infinity
solution more powerful. For instance, for address summary 5.*,
it might be configured for a count of 3, whereas for address
summary 12.13.* it might be configured for a count of 7. This
would say that when importing 5.*, unless there was at least one
address matching 5.* that had a region count of at most 2, then
5.* would not be reported. If this is not configured on a per
address summary basis, then each router would be configured with
a single region count limit that would apply to all address
summaries being imported.
6. Extra Information in Control Packets
6.1. Hello, CSNP, PSNP
These packets will contain an additional field, as an option,
which is "region name". If R has a link which is configured to
be in multiple regions, then R will not accept any control
packet on that link unless it has the "region name" option. But
for links which are configured to be in only a single region, a
packet that has no region name option will be accepted and
Perlman (Internet-Draft expires end December 1993) [Page 6]
Internet-Draft Multilevel IS-IS June 1993
assumed to be from that region. A packet received on link L with
a region name for which R has not been configured for L will be
rejected.
6.2. LSP
The LSP contains the region name option for specifying which
region the LSP belongs to (for the same purpose and used the
same way as the Hello, CSNP, and PSNP). Destinations reported in
an LSP are marked as "internal" or "external", plus there is a
"region count" which specifies the total number of regions
through which this information has been imported (to alleviate
the count-to-infinity problem.
7. Using Address Summaries
This is similar to the rules in integrated IS-IS for address
summaries for IP.
- For each (summary address), cost configured: If any address
matching that summary is reachable in any other region (as
known through the LSP database and Dijkstra calculation for
that region), then report that summary address as
reachable. If "cost" is configured, report the greater of
the configured value, or the cost of the nearest address
matching the summary as the cost. Otherwise, report the
cost to the nearest matching address. Mark the information
as "external".
- If "exceptions flag" is set, then report each reachable
address not already subsumed by one of the configured
summaries.
Note that we are assuming the IS-IS cost metric will be expanded
from 6 bits. We are importing a path cost, not a link cost, so
it must be possible to report a metric larger than 6 bits.
Suppose (5.*, cost 17) is configured into R as an address
summary to import into region B. Suppose 5.13.15 is reachable
in region A (R knows this because of R's region A LSP database
and Dijkstra calculation).
1. If 5.13.15 was internal in region A, then R would report
(5.*, 17, region count=1) in its LSP in region B.
2. If 5.13.15 was reported with a region count of 4 in A, then
Perlman (Internet-Draft expires end December 1993) [Page 7]
Internet-Draft Multilevel IS-IS June 1993
R would report a region count of 5 in its LSP in region B
for address prefix 5.*.
8. Picking a Path
Routing is always to longest matching address prefix, regardless
of cost, whether it's marked internal vs external, etc. When
calculating a path to address prefix D, one being an internal
path and one being an external path (and both being prefixes of
exactly the same length), then the internal path is preferred
regardless of cost. For instance, suppose D is announced in R1's
LSP in region A as being internal, and the path cost to D (cost
to R1, plus the link cost advertised in R1's LSP to D) is x. Now
suppose D is also announced in R2's LSP in region B, but as
being external, and the path cost to D (cost to the router
announcing D, plus the link cost in the LSP to D) is y. Then
regardless of the values of x or y, the packet is routed towards
R1.
9. Counting-to-Infinity
It is possible for region B to export address summary 5.13.14.*,
and have it (or a shorter prefix, like 5.*) reimported through
some other router. Especially if 5.13.14.* were to become
unreachable, this would lead to a loop where 5.13.14.* would be
reimported into B, exported via the same path as before, and
reimported, etc. Each time the cost would increase, but it
would take intolerably many iterations for the cost to increase
to a large enough value to know that the address prefix was
unreachable. So we include a region count.
If address summary 5.* is configured for import into region B,
and 5.12.* is reachable in region A, with a region count of 7,
and 5.15.17.* is reachable in region C with a region count of
10, then 5.* is imported into B, with a region count of 8. It
is somewhat worrisome that the region count for 5.15.17.* is
decreasing, but it will not be a problem because the only way
for a region count to decrease is if the address summary gets
shorter -- this cannot happen over and over, since the address
summary is only of finite length.
If the counting behavior is too intolerable even with the region
count, then we could configure per-address summary region
counts, or we could screen out importation of certain address
summaries that should not arrive from a particular direction.
Also, if routers are configured not to report anything other
than their configured address summaries, then it is possible to
eliminate loops (in most topologies).
Perlman (Internet-Draft expires end December 1993) [Page 8]
Internet-Draft Multilevel IS-IS June 1993
It might be tempting, in order to solve the counting problem, to
list an entire path of region names, instead of merely a region
count. This might make the count-to-infinity converge more
quickly. However, it would take too much room in the LSP
(especially if a text string is used for a region name instead
of, say, a one or two byte integer, globally assigned for
uniqueness). And it is not clear what to list as the region
name when, for instance, 5.* is being imported into B because
5.13.* is reachable in A and 5.15.* is reachable in C. Probably
the right thing would be to add both A and C to the list of
regions 5.* has been imported through. Another disadvantage of
listing the region names is that it requires region names to be
globally unique. Otherwise, a region name can be the same as
another region name provided that the two regions do not touch
(if they did, they'd merge).
It also might be tempting to put in the "original region name",
i.e. the region in which the address was internal. However,
this would not solve the count-to-infinity problem except in the
original region, and it is also not clear what to put as the
"original region name" when, as in the example in the previous
paragraph, 5.* might be being imported into B because 5.13.* was
reachable internally in A and 5.15.* was reachable internally in
C.
Other optimizations that might be explored are to limit which
routers import information. For instance, perhaps only the
router that can import an address summary with the lowest cost
should import that summary -- other routers would remove the
address from their LSPs when they noticed it reported in a
different router's LSP with lower cost. This would eliminate
some routes. For instance, if router R1 reports D as reachable
at cost 71 and router R2 reports D as reachable at cost 72, then
routers closer to R2 would be better off routing through R2 even
though R1 is closer to the destination (but the combined cost to
get to the router and from there to D is less good through R1).
Perhaps the right way to do the optimization of information
minimization is to add information to the configuration of an
address summary that tells R to report address summary D only if
R does not see D reported in another router's LSP in that region
at lower cost.
10. Working Group Information
The current co-chairs of the ISIS working group are:
Ross Callon
Wellfleet Communications Inc.
Perlman (Internet-Draft expires end December 1993) [Page 9]
Internet-Draft Multilevel IS-IS June 1993
2 Federal Street
Billerica
MA 01821
USA
Phone: (508) 436 3936
Email: rcallon@wellfleet.com
Chris Gunner
Digital Equipment Corp.
550 King Street
Littleton
MA 01460-1289
USA
Phone: (508) 486 7792
Fax: (508) 486 5279
Email: gunner@dsmail.enet.dec.com
The working group mailing list is:
isis@merit.edu
Subscription requests should be sent to:
isis-request@merit.edu
11. Authors' Addresses
Radia Perlman
Digital Equipment Corp.
550 King Street
Littleton
MA 01460-1289
USA
Phone: (508) 486 7648
Fax: (508) 486 5279
Email: perlman@dsmail.enet.dec.com
Chris Gunner
Digital Equipment Corp.
550 King Street
Littleton
MA 01460-1289
USA
Phone: (508) 486 7792
Fax: (508) 486 5279
Email: gunner@dsmail.enet.dec.com
Perlman (Internet-Draft expires end December 1993) [Page 10]